/*
https://leetcode.cn/problems/find-array-given-subset-sums/solution/cong-zi-ji-de-he-huan-yuan-shu-zu-by-lee-aj8o/
 */
import java.util.Arrays;

public class Solution1982 {

    public int[] recoverArray(int n, int[] sums) {
        Arrays.sort(sums);
        if (sums.length==2){
            if (sums[0]==0){
                return new int[]{sums[1]};
            }else if (sums[1]==0){
                return new int[]{sums[0]};
            }else {
                return new int[]{};
            }
        }
        int d=sums[1]-sums[0];
        int[] p1=new int[sums.length/2];
        int[] p2=new int[sums.length/2];
        int[] visit=new int[sums.length];
        int l=0,r=0;
        for (int i=0,j=0;i<sums.length;i++){
            if (visit[i]==0){
                visit[i]=1;
                p1[l++]=sums[i];
                while (sums[j]!=sums[i]+d || visit[j]==1){
                    j++;
                }
                p2[r++]=sums[j];
                visit[j]=1;
            }
        }
        int[] ans=recoverArray(n-1,p1);
        if (ans.length!=0){
            int[] o;
            o=Arrays.copyOf(ans,ans.length+1);
            o[ans.length]=d;
            return o;
        }
        ans=recoverArray(n-1,p2);
        if (ans.length!=0){
            int[] o;
            o=Arrays.copyOf(ans,ans.length+1);
            o[ans.length]=-d;
            return o;
        }
        return new int[]{};
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution1982().recoverArray(3, new int[]{-3, -2, -1, 0, 0, 1, 2, 3})));
    }
}
